/*
 * @lc app=leetcode.cn id=421 lang=typescript
 *
 * [421] 数组中两个数的最大异或值
 */

// @lc code=start

class TireNode {
  next: TireNode[];
  constructor() {
    this.next = new Array(2).fill(null);
  }
}

class Tire {
  root: TireNode;
  constructor() {
    this.root = new TireNode();
  }
  insert(num: number) {
    let cur = this.root;
    for (let i = 30; i >= 0; i--) {
      const bit = (num >> i) & 1;
      if (!cur.next[bit]) {
        cur.next[bit] = new TireNode();
      }
      cur = cur.next[bit];
    }
  }
  search(num: number): number {
    let cur = this.root;
    let res = 0;
    for (let i = 30; i >= 0; i--) {
      const bit = (num >> i) & 1;
      if (cur.next[+!bit]) {
        res |= 1 << i;
        cur = cur.next[+!bit];
      } else {
        cur = cur.next[bit];
      }
    }
    return res;
  }
}

function findMaximumXOR(nums: number[]): number {
  const tire = new Tire();
  // 构建 Tire
  for (const num of nums) {
    tire.insert(num);
  }
  let ans = 0;
  // 查找最大异或值
  for (const num of nums) {
    ans = Math.max(ans, tire.search(num));
  }
  return ans;
}
// @lc code=end
